package 剑指offer;

import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

import static 抽象数据类型.TreeNode.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-07
 */
public class 判断一棵二叉树是否为搜索二叉树和完全二叉树 {
    public static void main(String[] args) {
        Integer[] str = new Integer[]{47,30,21,14,11,45,4,26,3,40,35,34,2,23,24,16,37,8,39,13,15,31,25,22,46,10,28
                ,12,9,32,43,36,7,1,27,48,33,19,44,29,6,42,5,41,38,17,18,20,49};
        TreeNode treeNode = buildTree(new ArrayList<>(Arrays.asList(str)));
        System.out.println(MaxDept(treeNode));
        System.out.println(MinDept(treeNode));
        System.out.println(isBalanceTree(treeNode));
        System.out.println(isSearchTree(treeNode));
    }

    public static boolean[] judgeIt(TreeNode root) {
        return new boolean[]{isSearchTree(root), isBalanceTree(root)};
    }

    private static boolean isSearchTree(TreeNode root) {

        if (root == null) {
            return true;
        }
        if (root.left != null && (int) root.left.val > (int) root.val) {
            return false;
        }
        if (root.right != null && (int) root.right.val < (int) root.val) {
            return false;

        }
        if (root.left != null && root.right != null && findMax(root.left) > findMin(root.right)) {
            return false;
        }
        return isSearchTree(root.left) && isSearchTree(root.right);
    }

    public static int findMin(TreeNode root) {
        if (root != null && root.left == null) {
            return (Integer) root.val;
        }
        return findMin(root.left);
    }

    public static int findMax(TreeNode root) {
        if (root != null && root.right == null) {
            return (Integer) root.val;
        }
        return findMax(root.right);
    }

    private static boolean isBalanceTree(TreeNode root) {

        return false;
    }

    private static int MaxDept(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = MaxDept(root.left);
        int right = MaxDept(root.right);
        return Math.max(left, right) + 1;
    }
    public boolean judgeComplete(TreeNode root){
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        TreeNode pre=root;
        while(q.size()>0){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode node=q.poll();
                //前一个没有序号，后面一个有
                if(pre==null&&node!=null){
                    return false;
                }
                if(node!=null){
                    q.offer(node.left);
                    q.offer(node.right);
                }
                pre=node;
            }
        }
        return true;


    }

    private static int MinDept(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = MinDept(root.left);
        int right = MinDept(root.right);
        return Math.min(left, right) + 1;
    }
}
